HW#1 --- last modified February 06 2019 04:20:16..

Solution set.

Due date: Feb 11

Files to be submitted:
  Hw1.zip

Purpose: To gain experience with probabilistic analysis and our first randomized algorithms.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO1 -- Analyze or code a randomized algorithm

Specification:

This homework will consist of two parts, a written part and a coding part. Both parts will be submitted in the Hw1.zip file. The written part should be in a file Hw1.pdf. It should be typeset in a reasonable manner using a tool like LaTeX. For this part of the homework you should write solutions for the following questions. In what you turn in, first copy and paste the question, then write your solution to it beneath it.

1. Suppose we have access to a C function with protoype
   

   bool p_random();
   

   which returns 1 with probability `p` and 0 with probability `1-p`. Write a C function

   bool q_random();
   

   which is allowed to call the function p_random that returns 1 with probability 1/4 and 0 otherwise. p_random should be your only source of randomness in your code.
2. Suppose there are `n` listening devices on a line/network. These devices were not manufactured by a common company and there is no central registry or authority. Each device has access to its own physical random number generator which can be used to implement a function Random(a,b). Each device knows the number `n` and must choose an identifier and announce it without communicating with any of the other devices except for this one announcement. Give an algorithm to do this, such that there is a high probability that all announced identifiers are unique. Prove your algorithm has the properties you claim.
3. Suppose rather than choose a priority between 1 and `n^3` in our first random permutation algorithm, we had chosen a priority between 1 and `n^4`. Show with work what the odds would have been that all of the priorities were distinct.
4. A set of events `E_1, ..., E_n` is said to be `k`-wise independent if for any subset of variables of size `k`, `E_(i_1), ..., E_(i_k)`, we have
   `Pr{E_(i_1) cap ... cap E_(i_k)} = Pr{E_(i_1)} cdot Pr{E_(i_2)} cdot cdots cdot Pr{E_(i_k)}`
   Give a fixed finite sample space, and for that sample space, give a set of events which are 3-wise independent but not 4-wise independent.
5. Suppose we toss balls into one of `n` bins. Assume each bin is equally likely. Calculate with work the expected number of balls you would need to toss until some bin has three balls in it.

For the coding portion of this assignment, I want you to write a program GenerateAllPermutations.java. I, as the grader, will compile your submission from the command line using:

javac GenerateAllPermutations.java 

I have Java 7 installed on my laptop (no fancy Java 8 please). I will then run your program with various lines like:

java GenerateAllPermutations n mode

Here `n` is some positive integer and mode is either quiet or verbose. In verbose mode, your program should output a sorted list of all the permutations on the numbers 1 to n followed by the number of times a static method randomPermutation(n) was called during execution. For example,

java GenerateAllPermutations 3 verbose
123
132
213
231
312
321
9

If the mode is quiet then it just outputs the number of times randomPermutation(n) was called. To implement GenerateAllPermutations, I want you to implement int[] randomPermutation(n) using one of the algorithms from class for computing a random permutation. Then in a loop call this function and see if the returned permutation is one you have already found or not. If not, store it. Once `n!` distinct permutations have been found your program sorts these and outputs as described. Using your program, I would like you to conduct some experiments, write them up, and include these in Hw1.pdf as well as your answers to the written problem. For the first experiment, plot a graph of the number of calls to randomPermutation(n) as a function of `n`. For each value of `n` you plot do at least 10 trials and compute a standard deviation. I would also like you to plot standard deviations as a function of `n`. What can you conclude from these graphs? Do your results agree with what you'd expect from the coupon collection results from class?

Point Breakdown